package com.sourcetrip.algorithm.inter;

/**
 * 布隆过滤器
 * --
 * 这是针对特殊应用业务场景的，针对大数据的数据结构。
 * 场景：
 * 经常性地判断某个元素是否存在？
 * -> 可以用数组/hash 表快速查询，但是他们都太浪费空间了！（数组的扩容，hash 表的负载因子）
 * -> 需要一个时间复杂度低，占用内存较少的解决方案。
 * BloomFilter 空间利用率高的概率型数据结构，作用：判断一个元素一定不存在；可能存在
 * （当 bloomFilter tells exist,说明可能不存在；tells not exist 不存在是可信的）
 * 优缺点：
 * 优点-空间效率和查询时间都远远超过一般的算法；
 * 缺点-有一定的误判率，删除困难（似乎可以用计数删除，尚未深入研究）
 * 实质是通过很长的二进制向量（越长误判率越低）和一系列 hash 函数。
 * 常见应用：
 * 网页黑名单系统/垃圾邮件过滤系统/爬虫的网址判重系统/解决缓存穿透
 * --
 * 只有两个简单的接口：
 * put() 添加
 * contains()	查询
 * @param <E>
 */
public interface BloomFilter<E> {

	/**
	 * 添加元素
	 * @param ele
	 * @return
	 */
	boolean put(E ele);

	/**
	 * 查询元素是否在 bf 中
	 * @param ele
	 * @return
	 */
	boolean contains(E ele);
}
